package algorithms.leaning.class38;

import common.util.MyUtil;

/**
 * 小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
 * 1）能装下6个苹果的袋子
 * 2）能装下8个苹果的袋子
 * 小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。
 * 给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1
 *
 * @author guichang
 * @date 2021/7/17
 */

@SuppressWarnings("all")
public class Code1_找规律_买苹果 {

    public static void main(String[] args) {
        for (int i = 1; i <= 200; i++) {
            MyUtil.printf("{} 袋子数 {}", i, optimal(i));
        }
    }

    /**
     * 暴力解，从最大的8袋子开始
     */
    public static int force(int apples) {
        if (apples <= 0) {
            return -1;
        }
        int bag8 = (apples >> 3);
        int rest = apples - (bag8 << 3);
        while (bag8 >= 0) {
            // 剩下的刚好能被6整除
            if (rest % 6 == 0) {
                return bag8 + rest / 6;
            } else {
                bag8--;
                rest += 8;
            }
        }
        return -1;
    }

    /**
     * 根据规律找到的解法
     */
    public static int optimal(int apples) {
        if (apples <= 5 || (apples & 1) == 1) {
            return -1;
        }
        if (apples <= 17) {
            if (apples == 6 || apples == 8) {
                return 1;
            }
            if (apples == 12 || apples == 14 || apples == 16) {
                return 2;
            }
            return -1;
        }
        return (apples - 18) / 8 + 3;
    }


}